package 蓝桥杯算法;

public class day36 {
    public static void main(String[] args) {
        int[] father=new int[5];
        for(int i=0;i<5;i++){
            father[i]=i;
        }
        day36 a=new day36();
        int[][] arr={{1,2},{1,3},{2,4},{3,4}};
        for(int i=0;i<arr.length;i++){
            a.join(arr[i][0],arr[i][1],father);
        }
        //根就是最先出现的那个，只要有联系，就一定可以连接
        if(a.issame(1,4,father)){
            System.out.println("1");
        }
        else {
            System.out.println("0");
        }
        //冗余连接
        int[] father2=new int[3];
        int[][] arr2={{1,2},{2,3},{1,3}};
        a.init(father2);
        for(int i=0;i<arr.length;i++){
            a.join(arr[i][0],arr[i][1],father2);
        }
        a.issame2(1,3,father2);
    }

    public int find(int n,int[] father){
        if(n==father[n]){
            return n;//跟是自己
        }
        //如果不符合则继续查找
        else return father[n]=find(father[n],father);
    }
    public void join(int n,int m,int[] father){
       n=find(n,father);
       m=find(m,father);
       if(n==m){//说明他们的根相同
           return;
       }
       father[m]=n;
    }
    public boolean issame(int n,int m,int[] father){
        n=find(n,father);
        m=find(m,father);
        return n==m;
        //如果跟相同，则其互通
    }
    //冗余连接
    public void init(int[] father){
        for(int i=0;i<father.length;i++){
            father[i]=i;
        }
    }
    public int find2(int u,int[] father){
        if(u==father[u]){
            return u;
        }
        //继续找父亲的根
       return father[u]=find2(u,father);
    }
    public boolean issame2(int u,int n,int[] father){
        return find2(n,father)==find2(u,father);
    }
    public void join2(int u,int n,int[] father){
        //开始寻根
        int uroot=find2(u,father);
        int nroot=find2(n,father);
        if(uroot==nroot){
            System.out.println(u+"  "+n);
            return;
        }
        //增加新的根
        father[nroot]=uroot;

    }




}
